package lesson7;

public class Demo1 {
    public static void main(String[] args) {
        int[] arr1 = {1,2,4,6,8,3,2};
        printArr(arr1);
        quickSort(arr1,0,arr1.length-1);
        printArr(arr1);
    }

    static void printArr(int[] arr){
        for(int i = 0; i < arr.length; i++){
            System.out.print(arr[i]+"  ");
        }
        System.out.println();
    }

    static void quickSort(int[] arr,int begin,int end){
        int i,j,basePoint;
        //i要去存储起始位置
        //j要存储结束为止
        //temp存储基准点
        if(begin>=end){
            return;
        }

        basePoint = arr[begin];

        i = begin;
        j = end;
        while(i<j){
            while(j>i&&arr[j]>=basePoint){
                j--;
            }
            //3

            while(i<j && arr[i]<=basePoint){
                i++;
            }
            //

            //交换
            int temp = arr[j];
            arr[j] = arr[i];
            arr[i] = temp;
        }

        //如果执行到该步骤一定是i==j
        int temp =  arr[begin];
        arr[begin] = arr[i];
        arr[i] = temp;
        quickSort(arr,begin,i-1);
        quickSort(arr,i+1,end);
    }
}
